//进行版本管理
#include <bits/stdc++.h>

using namespace std;

int n;  // 城市个数
vector<vector<int>> A_hao;  // 城市间距离
vector<int> x;  // 记录路径
vector<int> bestx;  // 记录最优路径
int bestp = numeric_limits<int>::max();  // 最短路径长
int cp = 0;  // 当前路径长

void solve_TSP(int t) {
    if (t == n) {  // 所有城市都已经访问
        if (A_hao[x[n - 1]][x[0]] != 0 && cp + A_hao[x[n - 1]][x[0]] < bestp) {  // 城市相通，并且可以返回起点
            bestp = cp + A_hao[x[n - 1]][x[0]];
            bestx = x;
        }
    } else {
        for (int i = t; i < n; i++) {
            if (A_hao[x[t - 1]][x[i]] != 0 && cp + A_hao[x[t - 1]][x[i]] < bestp) {  // 约束和限界条件
                swap(x[t], x[i]);
                cp += A_hao[x[t - 1]][x[t]];
                solve_TSP(t + 1);
                cp -= A_hao[x[t - 1]][x[t]];
                swap(x[t], x[i]);
            }
        }
    }
}

int main() {
    cout << "输入城市个数: ";
    cin >> n;

    if (cin.fail() || n <= 0) {
        cout << "城市个数必须是大于0的整数" << endl;
        return -1;
    }

    A_hao.resize(n, vector<int>(n));
    x.resize(n);
    bestx.resize(n);

    for (int i = 0; i < n; i++) {
        x[i] = i;
    }

    cout << "输入城市之间的距离(0表示城市间不通):" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> A_hao[i][j];
            if (cin.fail() || A_hao[i][j] < 0) {
                cout << "距离必须是非负整数" << endl;
                return -1;
            }
        }
    }

    solve_TSP(1);  

    if (bestp == numeric_limits<int>::max()) {
        cout << "无解，无法找到有效路径。" << endl;
    } else {
        cout << "最短路径长度: " << bestp << endl;
        cout << "路径为: ";
        for (int i = 0; i < n; i++) {
            cout << bestx[i] + 1 << " ";  // 输出路径时加1
        }
        cout << bestx[0] + 1 << endl;  // 回到起点
    }
    
    return 0;
}